package _mst;

/**
 * 面试题 08.11. 硬币
 */
public class T0811 {
    public int waysToChange(int n) {
        int MOD = 1000000007;
        int[] coins = new int[]{1, 5, 10, 25};
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int coin : coins) {
            for (int c = coin; c < n + 1; c++) {
                f[c] = (f[c - coin] + f[c]) % MOD;
            }
        }
        return f[n];
    }
}
